Một nhà thờ nhỏ hình bát giác được Juvenal - Thượng phụ Chính thống giáo Hy Lạp của Jerusalem (dưới thời cai trị của hoàng đế Marcianus) - cho xây dựng trên vị trí tìm thấy trong thế kỷ thứ 5, và đã bị phá hủy trong cuộc xâm lược của Ba Tư năm 614.

Trong các thế kỷ sau nhà thờ đã bị phá hủy và xây dựng lại nhiều lần, nhưng hầm mộ vẫn còn nguyên. Đối với các người Hồi giáo khi cai trị vùng Đất Thánh, thì đây là nơi chôn cất người mẹ của tiên tri Isa (tức chúa Giêsu).

Sau đó nhà thờ được quân Thập tự chinh xây dựng lại trong năm 1130, cùng với một tu viện dòng Biển Đức có tường bao quanh gọi là "Tu viện Đức Bà của thung lũng Josaphat"[4]. Khu phức hợp tu viện bao gồm các cột theo kiến trúc Gothic, các tranh tường màu đỏ trên màu xanh lá cây, và 3 tòa tháp để bảo vệ. Cầu thang và lối vào cũng là một phần của nhà thờ thời "Thập tự chinh". Nhà thờ này đã bị Saladin phá hủy năm 1187, nhưng hầm mộ vẫn còn được tôn trọng; tất cả những gì còn lại là lối vào ở phía nam và cầu thang. Các phần đá và vữa xây dựng của nhà thờ này được sử dụng để xây các bức tường của Jerusalem.

Trong hậu bán thế kỷ 14, các tu sĩ dòng Phanxicô đã xây dựng lại nhà thờ một lần nữa. Năm 1757 các giáo sĩ Chính thống giáo Hy Lạp đã làm một cuộc tiếp quản các nơi thiêng liêng khác nhau trên Đất Thánh trong ngày Chúa Nhật Lễ Lá, trong đó có tu viện và nhà thờ này, đồng thời trục xuất các tu sĩ dòng Phanxicô[5]. Khi đế quốc Ottoman nắm quyền cai trị vùng Đất Thánh thì họ ủng hộ thỏa thuận "nguyên trạng" (statu quo) ở vùng Đất Thánh giữa các giáo hội khác nhau[6]. Kể từ đó, ngôi mộ Đức Trinh nữ Maria được đặt thuộc quyền sở hữu của Giáo hội Chính thống giáo Hy Lạp, trong khi hang đá ở vườn Gethsemani thuộc quyền sở hữu của dòng Phanxicô.